package chapter1;

import common.Node;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * create by yongli on 2021-07-08 09:14
 */

public class Section3 {
    public static void main(String[] args) {
        String[] strs = {"23","23232","89898"};
        String[] str2 ={"23"};
        Node<String> node = add(strs);
        Node<String> reverse = rr(node);
        print(reverse);
    }

    /**
     *
     * @param strs
     * @return
     */
    public static Node<String> add(String[] strs){
        Node<String> head = new Node();
        Node<String> cur = head;
        for(String str:strs){
            Node<String> n = new Node<>(str);
            cur.next = n;
            cur = n;
        }
        return head.next;
    }
    public static void print(Node node){
        while (node!=null){
            System.out.println(node.item);
            node = node.next;
        }
    }


    // 迭代翻转链表,node不为空
    public static Node<String> reverse(Node node){
        Node first = node;
        // revese<-first
        // r-->f ==> f<--r
        Node reverse = null;
        while (first!=null){
            Node second = first.next;
            first.next=reverse;
            //
            reverse = first;
            first = second;
        }
        return reverse;
    }

    // 使用链表本身的递归属性，中间递归
    // 递归是一个函数栈
    public static Node<String> rr(Node first){
        if(first==null){
            return null;
        }
        if(first.next==null){
            return first;
        }
        Node second = first.next;
        // first.next!=null
        Node rest = rr(second);
        // first --> rest 掉转头
        // 写代码有如神助
        second.next =first;
        first.next=null;
        return  rest;
    }




    /**
     * 要求表达式合法
     * @return
     */
    public static double Dijkstra(String expr){

        Deque<Double> nums = new ArrayDeque<>();
        Deque<String> ops =new ArrayDeque<>();

        // 忽略左括号，右括号时计算一次


        return nums.pop();
    }



    /**
     *
     * @param chars 括号字符,只包含（，）
     * @return 判断括号是否有效
     *
     * */
    public static boolean isValid(char[] chars){
        Deque<Character> stack= new ArrayDeque<>();
        // iterator
        for(char ch:chars){
            if(ch=='('){
                stack.push('(');
            }else{
                // 考虑了两个
                if(stack.size()<1 || stack.pop()!='('){
                    return false;
                }
            }
        }
        return stack.size()==0;
    }
}
